﻿// Median POJ - 3579.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stdio.h>

using namespace std;


//https://vjudge.csgrandeur.cn/problem/POJ-3579

/*
给定 N 个数 X1，X2，... , XN，让我们计算每对数的差值： ∣Xi - Xj∣ （1 ≤ i ＜ j ≤ N）。
通过这项工作，我们可以得到 C(N,2) 个差值，现在你的任务是尽快找出差值的中位数！

请注意，在这个问题中，中位数的定义是：如果 m（差值的数量）是偶数，则第 (m/2)-th 个最小的数。
例如，在 m = 6 的情况下，你必须找出第三个最小的数。

输入
输入由多个测试用例组成。
每个测试用例的第一行都会给出 N。然后给出 N 个数字，分别代表 X1、X2、... , XN, 
( Xi ≤ 1,000,000,000 3 ≤ N ≤ 1,00,000 )

输出
对每个测试用例，另起一行输出中位数。
*/

const int N = 100010;
int arr[N];
long long n;
long long  limit;


int  Getbelow(int c, int  x) {
	//二分获取小于等于x的 个数
	int  l = c; int  r = n;
	while (l < r) {
		int  mid = (l + r + 1) >> 1;
		if ((arr[mid] - arr[c]) <= x) {
			l = mid;
		}
		else {
			r = mid - 1;
		}
	}
	return l - c;
}

bool check(long long  x) {
	long long  res = 0;
	for (int i = 1; i <= n; i++) {
		res += Getbelow(i, x);
	}

	if (res < limit) {
		return false;
	}

	return true;
}

void solve() {
	int  l = 0;
	int  r = arr[n] - arr[1] + 10;
	arr[0] = -1;
	limit = n * (n - 1) / 2 / 2;
	if ((n * (n - 1) / 2 % 2) != 0) limit++;

	while (l < r) {
		long long  mid = l + r >> 1;
		if (check(mid)) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	printf("%d\n", l);
}


int main()
{
	while (~scanf("%d", &n)) {
		for (int i = 1; i <= n; i++) { scanf("%d", &arr[i]); }
		sort(arr + 1, arr + 1 + n);
		solve();
	}

	return 0;
}